package h0829;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class PartitionPalinDromeString {
    private static boolean isPalindrome(String s, int start, int end) {
        end--; // end is exclusive in the substring method, so adjust it for palindrome check.
        while (start < end) {
            if (s.charAt(start) != s.charAt(end)) {
                return false;
            }
            start++;
            end--;
        }
        return true;
    }


    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        System.out.println(getRes(s));
    }

    private static List<LinkedList<String>> getRes(String s) {
        List<LinkedList<String>> res = new ArrayList<>();
        LinkedList<String> temp = new LinkedList<>();
        int start = 0;
        backTrack(res, temp, start, s);
        return res;
    }

    private static void backTrack(List<LinkedList<String>> res, LinkedList<String> temp, int start, String s) {
        if (start == s.length()) {
            res.add(new LinkedList<>(temp));
        }
        //尝试所有的分割情况
        for (int end = start + 1; end <= s.length(); end++) {
            //这里先判断是否是回文，再进行截取，提高了效率，避免了非回文状态下字符串的截取。
            if (isPalindrome(s,start,end)){
                temp.addLast(s.substring(start,end));
                //TODO 尤其注意这里是end
                backTrack(res, temp, end, s); //回溯
                temp.removeLast();
            }
            else {
                continue;
            }
        }
    }
}
